package com.kevin.Code.BFS;

import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;

/**
 * @author Vinlee Xiao
 * @Classname OpenTheLock
 * @Description Leetcode 752 打开锁盘  中等难度 bfs 广度优先遍历
 * @Date 2021/9/23 16:12
 * @Version 1.0
 */
public class OpenTheLock {

    public static void main(String[] args) {
        OpenTheLock lock = new OpenTheLock();
        String s = lock.plusOne("0000", 3);
        System.out.println(s);
    }

    /**
     * @param deadends
     * @param target
     * @return
     */
    public int openLock(String[] deadends, String target) {

        //用于记录转动的次数
        int step = 0;
        //用于记录是否重复访问
        HashSet<String> visited = new HashSet<>();
        HashSet<String> deadLock = new HashSet<>();
        Deque<String> queue = new LinkedList<String>();

        //添加进队列中
        queue.addLast("0000");
        visited.add("0000");

        for (String deadend : deadends) {
            deadLock.add(deadend);
        }

        while (!queue.isEmpty()) {

            int size = queue.size();
            for (int i = 0; i < size; i++) {

                String s = queue.pollFirst();

                if (deadLock.contains(s)) {
                    continue;

                }

                if (s.equals(target)) {
                    return step;
                }

                //每次转动一共有8种可能
                for (int j = 0; j < 4; j++) {
                    //对字符串进行加操作的结果
                    String s1 = plusOne(s, j);

                    if (!visited.contains(s1)) {
                        queue.addLast(s1);
                        visited.add(s1);
                    }
                    //对字符串进行减操作的结果
                    String s2 = subtractOne(s, j);

                    if (!visited.contains(s2)) {
                        queue.addLast(s2);
                        visited.add(s2);
                    }


                }


            }
            //增加步数
            step++;

        }

        return -1;
    }


    /**
     * @param c
     * @param index
     */
    private String plusOne(String c, int index) {

        char[] ch = c.toCharArray();

        if (ch[index] == '9') {
            ch[index] = '0';
        } else {
            ch[index] = (char) (ch[index] + 1);

        }

        return new String(ch);
    }

    /**
     * @param c
     * @param index
     */
    private String subtractOne(String c, int index) {

        char[] ch = c.toCharArray();

        if (ch[index] == '0') {
            ch[index] = '9';
        } else {
            ch[index] = (char) (ch[index] - 1);

        }

        //将字符串数组转换为字符串
        return new String(ch);
    }

}
